package doublepointer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname : FindAllAnagramsInAString
 * @Description : 438. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 * @Author : cty
 * @Date 2023/4/14 23:53
 */


public class FindAllAnagramsInAString {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] cnt = new int[128];
        for (int c : p.toCharArray()) cnt[c]++;
        int l = 0, r = 0;
        while(r < s.length()) {
            if (cnt[s.charAt(r)] > 0) {
                // r走过的一定是l走过的 或 相差的p的字母
                // 遇到p的异位词的子串，r会一直往右走直至与r相差p的长度
                cnt[s.charAt(r++)]--;
                if (r - l == p.length()) res.add(l);
            } else {
                // 遇到非在p中的字母，l可能会走到r的前面，但是下次循环也一定被r赶上
                cnt[s.charAt(l++)]++;
            }
        }
        return res;
    }
}
